struct Sieve {
	Sieve(const int n) : st_(n + 1), minp_(n + 1) {
    st_[1] = true;
		for (int i = 2; i <= n; i++) {
			if (!st_[i]) {
				primes_.emplace_back(i);
				minp_[i] = i;
			}
			for (int j = 0; 1ll * primes_[j] * i <= n; j++) {
				int v = primes_[j] * i;
				st_[v] = true;
				minp_[v] = primes_[j];
				if (i % primes_[j] == 0) {
					break;
				}
			}
		}
	}

	int kth(const int k) {
		assert(k <= (int)primes_.size());
		return primes_[k - 1];
	}

	int f(const int p) {
		assert(p <= (int)st_.size());
		return minp_[p];
	}

	vector<pair<int, int>> getPrimeFactor(int v) {
		unordered_map<int, int> fac_counter;
		while (v > 1) {
			fac_counter[f(v)]++;
			v /= f(v);
		}
		return {fac_counter.begin(), fac_counter.end()};
	}

  vector<int> getPrimeFactors(int v) {
		vector<int> fac;
    while (v > 1) {
			fac.emplace_back(f(v));
			v /= f(v);
		}
		return fac;
	}

	vector<int> getFactor(const int x, const int l, const int r) {
		auto fac = getPrimeFactor(x);
		vector<int> result;
		auto find = [&](auto &&self, int f, int v) {
			if (f == (int)fac.size()) {
				if (v >= l) {
					result.emplace_back(v);
				}
				return;
			}
			self(self, f + 1, v);
			int cnt = 0;
			while (cnt < fac[f].second) {
				if (1ll * v * fac[f].first > r) {
					break;
				}
				v *= fac[f].first;
				cnt++;
				self(self, f + 1, v);
			}
		};
		find(find, 0, 1);
		return result;
	}

  bool is_prime(int x) {
    return st_[x];
  }
	vector<bool> st_;
	vector<int> primes_, minp_;
};
Sieve p(2000000);
void solve()
{
  int n, m;
  cin >> n >> m;

  vi a(n + 1);
  rep(i, 1, n) {
    cin >> a[i];
  }

  vvi g(n + 1), q(n + 1);
  vector<vector<pii>> cnt(2000001);
  vi ans(m + 1, -1), deg(m + 1, -1);
  auto dfs = [&](auto &&dfs, int u, int fa, int dep) -> void {
    auto f = p.getPrimeFactor(a[u]);
    for (auto &[x, c] : f) {
      for (auto &id : q[u]) {
        if (sz(cnt[x])) {
          auto [p, d] = cnt[x].back();
          if (deg[id] < d) {
            deg[id] = d;
            ans[id] = p;
          }
        }
      }
      cnt[x].eb(u, dep);
    }
    for (auto &v : g[u]) {
      if (v != fa) {
        dfs(dfs, v, u, dep + 1);
      }
    }
    for (auto &[x, c]: f) {
      cnt[x].pop_back();
    }
  };

  auto sett = [&](int p, int w) {
    dfs(dfs, 1, 0, 0);
    rep(i, 1, n) {
      q[i].clear();
    }
    a[p] = w;
  };

  rep(i, 2, n) {
    int u, v;
    cin >> u >> v;
    g[u].eb(v);
    g[v].eb(u);
  }

  rep(i, 1, m) {
    int op, u, v;
    cin >> op;
    if (op == 1) {
      cin >> u;
      q[u].pb(i);
    } else {
      cin >> u >> v;
      ans[i] = 0;
      sett(u, v);
    }
  }

  sett(1, 0);
  rep(i, 1, m) {
    if (!ans[i]) {
      continue;
    }
    cout << ans[i] << '\n';
  }
}